package org.example.algorithm.backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class PermuteSolution {

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        PermuteSolution solution = new PermuteSolution();
        List<List<Integer>> res = solution.permute(nums);
        System.out.println(res);
    }

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len==0) {
            return res;
        }
        List<Integer> list = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        doPermute(res, nums, 0, list, set);
        return res;
    }

    private void doPermute(List<List<Integer>> res, int[] nums, int index, List<Integer> list, HashSet<Integer> set) {
        if (index == nums.length) {
            res.add(new ArrayList<>(list));
        } else {
            for (int i=0;i<nums.length;i++) {
                if (set.contains(nums[i])) {
                    continue;
                }
                list.add(nums[i]);
                set.add(nums[i]);
                doPermute(res, nums, index+1, list, set);
                list.remove(list.size()-1);
                set.remove(nums[i]);
            }
        }
    }
}
